{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": "true"
   },
   "source": [
    "# Table of Contents\n",
    "<div class=\"lev1 toc-item\"><a href=\"#Exercise-4.4.-Newton's-method-I\" data-toc-modified-id=\"Exercise-4.4.-Newton's-method-I-4\"><span class=\"toc-item-num\">4&nbsp;&nbsp;</span>Exercise 4.4. Newton's method I</a></div><div class=\"lev1 toc-item\"><a href=\"#Exercise-4.6.-Finding-square-roots\" data-toc-modified-id=\"Exercise-4.6.-Finding-square-roots-6\"><span class=\"toc-item-num\">6&nbsp;&nbsp;</span>Exercise 4.6. Finding square roots</a></div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# import basic librariees and autograd wrapped numpy\n",
    "import sys\n",
    "sys.path.append('../')\n",
    "import autograd.numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# this is needed to compensate for matplotlib notebook's tendancy to blow up images when plotted inline\n",
    "%matplotlib notebook\n",
    "from matplotlib import rcParams\n",
    "rcParams['figure.autolayout'] = True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercise 4.4. Newton's method I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this exercise you will perform Newton's method to minimize the function\n",
    "\n",
    "\\begin{equation}\n",
    "g(w) = \\frac{1}{50}\\left(w^4 + w^2 + 10w \\right) + 0.5\n",
    "\\end{equation}\n",
    "\n",
    "beginning at the point $w = 2.5$ marked as a magenta dot (and corresponding evaluation of the function marked as magenta X).  Just a few iterations should do the trick!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A skeleton of the desired algorithm is in the cell below.  All parts marked \"TO DO\" are for you to construct."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "# using an automatic differentiator - like the one imported via the statement below - makes coding up gradient descent a breeze\n",
    "from autograd import grad \n",
    "from autograd import hessian\n",
    "\n",
    "# newtons method function - inputs: g (input function), max_its (maximum number of iterations), w (initialization)\n",
    "def newtons_method(g,max_its,w,**kwargs):\n",
    "    # compute gradient module using autograd\n",
    "    gradient = grad(g)\n",
    "    hess = hessian(g)\n",
    "    \n",
    "    # set numericxal stability parameter / regularization parameter\n",
    "    epsilon = 10**(-10)\n",
    "    if 'epsilon' in kwargs:\n",
    "        epsilon = kwargs['epsilon']\n",
    "\n",
    "    # run the newtons method loop\n",
    "    weight_history = [w]           # container for weight history\n",
    "    cost_history = [g(w)]          # container for corresponding cost function history\n",
    "    for k in range(max_its):\n",
    "        # evaluate the gradient and hessian\n",
    "        ## TO DO \n",
    "\n",
    "        # reshape hessian to square matrix for numpy linalg functionality\n",
    "        ## TO DO\n",
    "        \n",
    "        # solve second order system system for weight update\n",
    "        A = hess_eval + epsilon*np.eye(w.size)\n",
    "        b = grad_eval\n",
    "        w = np.linalg.solve(A,np.dot(A,w) - b)\n",
    "        \n",
    "        # record weight and cost\n",
    "        weight_history.append(w)\n",
    "        cost_history.append(g(w))\n",
    "    return weight_history,cost_history"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Plot the cost funciton history of this minimization to ensure you have reached the global minimum."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercise 4.6. Finding square roots"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we want to find the zero-crossing of the function\n",
    "\n",
    "\\begin{equation}\n",
    "g(w) = w^2 - 999\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To do this you will use generic Newton's method, treating this as a derivative function - i.e., as $g^{\\prime}(w)$.  This means we wish to apply Newton's method to the *antiderivative* of the function above\n",
    "\n",
    "\\begin{equation}\n",
    "f(w) = \\frac{1}{3}w^3 - 999w + C\n",
    "\\end{equation}"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.10"
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "navigate_num": "#000000",
    "navigate_text": "#333333",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700",
    "sidebar_border": "#EEEEEE",
    "wrapper_background": "#FFFFFF"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "196.767px",
    "width": "251.1px"
   },
   "navigate_menu": true,
   "number_sections": false,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": true,
   "toc_section_display": "block",
   "toc_window_display": false,
   "widenNotebook": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
